The present invention relates generally to data routing systems, and more particularly to a method and apparatus for routing packets through a network.
In a packet switched network, a router is a switching device that receives a packet on an input line card and switches it to an output line card. Routers perform this switching function by evaluating header information at the beginning of the packet in order to determine the proper output line card for that packet. A line card can include both input ports and output ports. That is, each line card can be configured to both transmit and receive packets.
Packet traffic received by a router in the middle of a network has no predictable patterns. Packets can flow from any input line card to any output line card. Given this chaotic behavior, routers can experience instantaneous congestion at their output line cards independent of their internal design.
As a consequence, routers include buffering to handle this instantaneous contention. Contention occurs when the router receives more packets addressed to an output line card than the output line card can handle. Typically, the minimum amount of buffering is equal to the minimum end-to-end network delay multiplied by the aggregate bandwidth of the router.
A key problem in designing routers is to make them scale to a large aggregate bandwidth. There are two ways to ways to do this, increasing the speed of individual line cards and increasing the number of line cards. Technology places hard limits on the speed of individual line cards, so the only way scale throughout is to increase the number of line cards.
Two conventional approaches to designing a router include a central memory approach and a central switch approach. In the central memory approach, all of the buffering for the router is provided by a single logically-centralized memory buffer with little or none provided by the individual line cards. In the central switch approach, input and output line cards are coupled by a switch fabric where each line card provides delay-bandwidth buffering. The switch fabric typically includes no buffering. The central memory approach is lower cost, but the central switch approach is easier to scale to greater numbers of line cards.
In the central switch approach, the problem of building a scalable router reduces to a problem of building a scalable switch fabric. A conventional router built in accordance with the central switch approach is shown in FIG. 1 and includes a control path 10 and a data path 12. The router includes a switch fabric 24 controlled by a centralized controller 22. Each of the input line cards 26 send requests for bandwidth to centralized controller 22 and each of the output line cards 28 indicates the availability of bandwidth (the control path). The centralized controller 22 operates to match the requests and availability in a way that is non-blocking and fair. A switch fabric is non-blocking if two streams of packets that start and end at different line cards do not interfere with each other inside of the switch fabric. A switch fabric is fair if two or more streams of packets converging on a single output line card are given an equal share of the output line card's bandwidth by the switch fabric. Depending on the decisions made by the centralized controller 22, packets are transferred from the input line cards through the switch fabric to the output line cards (the data path).
A centralized controller works well for a relatively small router, however it rapidly becomes unimplementable with increases in the number of line cards. The storage and processing requirements of the central controller grow at least as the square of the number of line cards, making this approach of limited utility in scaling routers to a large size.